#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <set>

using namespace std;

  struct ListNode {
      int val;
      ListNode *next;
      ListNode(int x) : val(x), next(NULL) {}
  };

  struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
      TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  };

TreeNode *listToBST(ListNode *&head, int start, int end)
{
    if (start > end) return NULL;
    int mid = start + (end-start)/2;
    TreeNode *l = listToBST(head, start, mid-1);
    TreeNode *node = new TreeNode(head->val);
    node->left = l;
    head = head->next;
    node->right = listToBST(head, mid+1, end);
    return node;
}

int getLen(ListNode *head)
{
    int len = 0;
    while(head) {
        len++;
        head = head->next;
    }
    return len;
}

class Solution {
public:
    TreeNode *sortedListToBST(ListNode *head) {
       int len = getLen(head); 
       return listToBST(head, 0, len-1);
    }
};


//pass all the test
int main(int argc, char **argv)
{

}
